#include <iostream>
#include <list>

using namespace std;

const int NODE_NUM = 6;

class AdjacencyNode; // Adjacency list node
class GNode; // Graphics node

bool isTraversed(GNode*, list<GNode*>&);
bool findAllNodes(GNode *[NODE_NUM], list<GNode*> &);

// Error C2683: 'dynamic_cast' : 'BaseNode' is not a polymorphic type
class BaseNode{
public:
	int node;
	BaseNode *next;	

	BaseNode(int node, BaseNode *next) : node(node), next(next){}

	virtual void print(){
		cout << "Node: " << node << ", next: " << next << endl;
	}
};

class GNode : public BaseNode{
public:
	GNode(int number = 1) : BaseNode(number, NULL){}
};

class AdjacencyNode : public BaseNode{
public:
	int weight;

	AdjacencyNode(int node, int weight = 1) : BaseNode(node, NULL), weight(weight){}

	void print(){
		cout << "Node: " << node << ", weight" << weight << ", next: " << next << endl;
	}
};

// Find a path which traverses all of the node
bool find(GNode *arr[NODE_NUM], list<BaseNode*> &assistList, list<GNode*> &nodeList){
	if(assistList.empty())
		return false;

	GNode *gNode = dynamic_cast<GNode*>(assistList.back());
	// GNode
	if(NULL != gNode){
		if(NULL != gNode->next){
			assistList.push_back(gNode->next);
			find(arr, assistList, nodeList);
		}else{
			assistList.pop_back();
			BaseNode *node = assistList.back();
			// If node->next is NULL
			while(NULL == node->next)
			{
				assistList.pop_back();
				assistList.pop_back();
				nodeList.pop_back();
				if(assistList.empty())
					return false;
				node = assistList.back();
			}
			assistList.pop_back();
			assistList.push_back(node->next);
			return find(arr, assistList, nodeList);
		}
	}
	else{ // Adjacency list node
		AdjacencyNode *lNode = dynamic_cast<AdjacencyNode*>(assistList.back());
		
		// The node current lNode points to has traversed
		if(isTraversed(arr[lNode->node], nodeList)){
			// Backtrack
			while(NULL == lNode->next){
				assistList.pop_back();
				assistList.pop_back();
				nodeList.pop_back();
				lNode = dynamic_cast<AdjacencyNode*>(assistList.back());
			}
			assistList.pop_back();
			assistList.push_back(lNode->next);
		}
		else{
			assistList.push_back(arr[lNode->node]);
			nodeList.push_back(arr[lNode->node]);

			// Find the path, return
			if(findAllNodes(arr, nodeList))
				return true;
		}
		return find(arr, assistList, nodeList);
	}
}

// Traverse the node or not
bool isTraversed(GNode *node, list<GNode*> &nodeList){
	if(NULL == node)
		return false;

	if(nodeList.empty())
		return false;

	for(list<GNode*>::iterator it = nodeList.begin(); it != nodeList.end(); ++it){
		if(node == *it)
			return true;
	}

	return false;
}

// nodeList constains all of the graphics nodes
bool findAllNodes(GNode *arr[NODE_NUM], list<GNode*> &nodeList){
	if(nodeList.empty())
		return false;
	if(nodeList.size() != NODE_NUM)
		return false;
	list<GNode*>::iterator it;
	for(int i = 0; i < NODE_NUM; ++i){
		for(it = nodeList.begin(); it != nodeList.end(); ++it){
			if(*it == arr[i])
				break;
		}
		if(it == nodeList.end())
			return false;
	}
	return true;
}

int gpmain(){
	// http://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg
	// Array of the graphics nodes
	GNode *arr[NODE_NUM];
	// Initialize the array
	for(int i = 0; i < NODE_NUM; ++i)
		arr[i] = new GNode(i + 1);	

	// Links among the nodes, create each node's adjacency list
	// 1 -> 2
	// 1 -> 5
	arr[0]->next = new AdjacencyNode(1);
	arr[0]->next->next = new AdjacencyNode(4);

	// 2 -> 1
	// 2 -> 3
	// 2 -> 5
	arr[1]->next = new AdjacencyNode(0);
	arr[1]->next->next = new AdjacencyNode(2);
	arr[1]->next->next->next = new AdjacencyNode(4);

	// 3 -> 2
	// 3 -> 4
	arr[2]->next = new AdjacencyNode(1);
	arr[2]->next->next = new AdjacencyNode(3);

	// 4 -> 3
	// 4 -> 5
	// 4 -> 6
	arr[3]->next = new AdjacencyNode(2);
	arr[3]->next->next = new AdjacencyNode(4);
	arr[3]->next->next->next = new AdjacencyNode(5);

	// 5 -> 1
	// 5 -> 2
	// 5 -> 4
	arr[4]->next = new AdjacencyNode(0);
	arr[4]->next->next = new AdjacencyNode(1);
	arr[4]->next->next->next = new AdjacencyNode(3);

	// 6 -> 4
	arr[5]->next = new AdjacencyNode(3);


	list<BaseNode*> assistList;
	list<GNode*> nodeList;
	assistList.push_back(arr[1]);
	nodeList.push_back(arr[1]);

	bool result = find(arr, assistList, nodeList);

	for(list<GNode*>::iterator it = nodeList.begin(); it != nodeList.end(); it++)
		(*it)->print();

	cout << endl << endl;

	for(list<BaseNode*>::iterator it = assistList.begin(); it != assistList.end(); ++it)
	{
		(*it)->print();
	}

	return 0;
}



/*void find(GNode *arr[5], list<GNode*> &nodeList){
	
	// nodeList.push_back(arr[0]);
	list<BaseNode*> tempNodeList;
	tempNodeList.push_back(arr[0]);
	if(NULL == arr[0]->next)
		return;

	tempNodeList.push_back(arr[0]->next);

	// GNode *top = NULL;
	GNode *top = dynamic_cast<GNode*>(tempNodeList.back());
	if(NULL != top)

	tempNodeList.push_back(arr[0]);
	do{	
		// Isolated node
		if(NULL == top->next){
			nodeList.pop_back();
			continue;
		}
	}
	while(!nodeList.empty());
	
}*/

/*
void find(GNode *arr[5], list<BaseNode*> &assistList, list<GNode*> &nodeList){
	if(assistList.empty())
		return;

	GNode *gNode = dynamic_cast<GNode*>(assistList.back());
	// GNode
	if(NULL != gNode){
		if(isTraversed(gNode, nodeList))
		{
			assistList.pop_back();
			BaseNode *node = assistList.back();
			assistList.pop_back();
			if(NULL != node->next)
				assistList.push_back(node->next);			
		}
		else{
			nodeList.push_back(gNode);
			assistList.push_back(gNode->next);
		}
		find(arr, assistList, nodeList);
	}
	else{ // a adjacency list node
		AdjacencyNode *lNode = dynamic_cast<AdjacencyNode*>(assistList.back());
		
		// The node current lNode points to has traversed
		if(isTraversed(arr[lNode->node], nodeList)){
			if(NULL == lNode->next){
				assistList.pop_back(); // pop up the AdjacencyNode
				assistList.pop_back(); // pop up the GNode
				nodeList.pop_back(); // pop up the GNode
			}else{
				assistList.pop_back();
				assistList.push_back(lNode->next);
			}
		}
		else{
			assistList.push_back(arr[lNode->node]);
			// nodeList.push_back(arr[lNode->node]);
		}
		find(arr, assistList, nodeList);
	}
}*/


/*
class AdjacencyListNode;

class GNode{
public:
	int nodeNum;
	AdjacencyListNode *next;

	GNode(int number = 1, AdjacencyListNode *node = NULL) : nodeNum(number), next(node){}
};

class AdjacencyListNode{
public:
	int index;
	AdjacencyListNode *next;

	AdjacencyListNode(int number = 1, AdjacencyListNode *node = NULL) : index(number), next(node){}
};
*/

// enum NodeType{Graphic = 0, AdjacencyList};
